package collections.tree;

import java8.TreePrintUtil;

public class MyRBT {
    /*
     * 打印"红黑树"
     *
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(Node tree, int key, int direction) {

        if (tree != null) {

            if (direction == 0)    // tree是根节点
                System.out.printf("%2d(B) is root\n", tree.key);
            else                // tree是分支节点
                System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree) ? "R" : "B", key, direction == 1 ? "right" : "left");

            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    public void print() {
        System.out.println("=========打印tree===========");
        if (root != null)
            print(root, root.key, 0);
        System.out.println("=========打印结束===========");
    }

    public static void main(String[] args) {
        MyRBT bst = new MyRBT();
        bst.insert(10);
        bst.insert(17);
        bst.insert(11);
        bst.insert(14);
//        bst.insert(12);
        bst.insert(3);
        bst.insert(33);
        bst.insert(38);
        bst.insert(0);
        bst.insert(99);
        bst.insert(100);
//        bst.insert(15);
        bst.print();

        System.out.println("开始删除");
        bst.remove(17);
        bst.print();
        bst.remove(10);
        bst.remove(11);
        bst.remove(38);
        bst.remove(14);
//        bst.insert(12);
        bst.remove(3);
        bst.remove(33);
        bst.remove(0);
        bst.remove(99);
        bst.remove(100);
//        bst.remove(15);
        bst.print();

//        System.out.println("删除99");
//        bst.remove(99);
//        TreePrintUtil.pirnt(bst.root);
//
//        System.out.println("再删除17");
//        bst.remove(17);
//        TreePrintUtil.pirnt(bst.root);
    }

    Node root;
    public static final boolean BLACK = true;
    public static final boolean RED = false;

    public void insert(int key) {
        Node lastParent = null;
        Node tmp = root;
        if (root == null) {
            Node n = new Node();
            n.key = key;
            n.color = BLACK;
            root = n;
            return;
        }

        while (tmp != null) {
            lastParent = tmp;
            if (key < tmp.key) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }

        boolean parentColor = lastParent.color;
        Node n = new Node();
        n.parent = lastParent;
        n.key = key;
        if (lastParent.key < key) {
            lastParent.right = n;
        } else {
            lastParent.left = n;
        }

        if (parentColor == BLACK) {
            return;
        } else {
            fixInsert(n);
        }
    }

    public void fixInsert(Node n) {
        Node parent = null;
        Node gp = null;
        Node uncle = null;
        int debugCnt = 1;
        System.out.println(n);
        while (root != n && isRed(parent = n.parent)) {
            debugCnt++;
            gp = parent.parent;
            if (parent == gp.left) {
                uncle = gp.right;
                // 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
                // (01) 将“父节点”设为黑色。
                //(02) 将“叔叔节点”设为黑色。
                //(03) 将“祖父节点”设为“红色”。
                //(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
                if (isRed(parent) && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gp);
                    n = gp;
                    continue;
                }

                //当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
                // (01) 将“父节点”作为“新的当前节点”。
                //(02) 以“新的当前节点”为支点进行左旋。
                if (isRed(parent) && isBlack(uncle) && parent.right == n) {
                    n = parent;
                    rotateLeft(n);
                    continue;
                }

                // 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
                //(01) 将“父节点”设为“黑色”。
                //(02) 将“祖父节点”设为“红色”。
                //(03) 以“祖父节点”为支点进行右旋。
                if (isRed(parent) && isBlack(uncle) && parent.left == n) {
                    setBlack(parent);
                    setRed(gp);
                    rotateRight(gp);
                }
            } else {
                uncle = gp.left;
                if (isRed(parent) && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gp);
                    n = gp;
                    continue;
                }
                if (isRed(parent) && isBlack(uncle) && parent.left == n) {
                    n = parent;
                    rotateRight(n);
                    continue;
                }
                if (isRed(parent) && isBlack(uncle) && parent.right == n) {
                    setBlack(parent);
                    setRed(gp);
                    rotateLeft(gp);
                }
            }
        }
        setBlack(root);
        System.out.println("fixInsert Cnt:" + debugCnt);

    }

    public void rotateLeft(Node n) {
        Node y = n.right;
        n.right = y.left;
        if (y.left != null) {
            y.left.parent = n;
        }

        y.parent = n.parent;
        if (n.parent == null) {
            root = y;
        } else {
            if (n.parent.left == n) {
                n.parent.left = y;
            } else {
                n.parent.right = y;
            }
        }

        y.left = n;
        n.parent = y;
    }

    public void rotateRight(Node n) {
        Node y = n.left;
        n.left = y.right;
        if (y.right != null) {
            y.right.parent = n;
        }

        y.parent = n.parent;
        if (n.parent == null) {
            root = y;
        } else {
            if (n.parent.left == n) {
                n.parent.left = y;
            } else {
                n.parent.right = y;
            }
        }

        y.right = n;
        n.parent = y;
    }

    public boolean isRed(Node n) {
        return !isBlack(n);
    }

    public boolean isBlack(Node n) {
        return n == null || n.color == BLACK;
    }

    public void setBlack(Node n) {
        if (n != null) {
            n.color = BLACK;
        }
    }

    public void setRed(Node n) {
        if (n != null) {
            n.color = RED;
        } else {
            throw new IllegalStateException("node为null, 不能设置成red");
        }
    }

    public boolean colorOf(Node n) {
        if(n == null) {
            return BLACK;
        }
        return n.color;
    }


//    public void remove(int key) {
//        Node tmp = root; // 要删除掉的节点
//        if (root == null) {
//            return;
//        }
//
//        boolean find = false;
//        while (tmp != null) {
//            if (tmp.key == key) {
//                find = true;
//                break;
//            } else if (key < tmp.key) {
//                tmp = tmp.left;
//            } else {
//                tmp = tmp.right;
//            }
//        }
//        if (!find) {
//            return;
//        }
//
//        Node successor = null;
//        Node successorParent = null;
//        Node child = null;
//        // 删除的节点没有左右节点
//        if (tmp.left == null && tmp.right == null) {
//            if (tmp == root) {
//                root = null;
//                return;
//            } else if (tmp == tmp.parent.left) {
//                tmp.parent.left = null;
//                child = null;
//                successorParent = tmp.parent;
//            } else {
//                tmp.parent.right = null;
//                child = null;
//                successorParent = tmp.parent;
//            }
//        }
//
//        // 删除的节点只有1个子节点
//        if (tmp.left == null) { // tmp有右孩子
//            successor = findSuccessor(tmp);
//            child = successor.right;
//            successorParent = successor.parent;
//            if(successorParent == tmp) {
//                successorParent = successor;
//            }
//            if (tmp == root) {
//
//            } else if (tmp == tmp.parent.left) { // tmp是父的左节点
//                tmp.parent.left = tmp.right;
//                tmp.right.parent = tmp.parent;
//            } else { // tmp是父的右节点
//                tmp.parent.right = tmp.right;
//                tmp.right.parent = tmp.parent;
//            }
//        } else if (tmp.right == null) { // tmp有左孩子
//            successor = findSuccessor(tmp);
//            child = successor.left;
//            successorParent = successor.parent;
//            if(successorParent == tmp) {
//                successorParent = successor;
//            }
//            if (tmp == root) {
//
//            } else if (tmp == tmp.parent.left) { // tmp是父的左节点
//                tmp.parent.left = tmp.left;
//                tmp.left.parent = tmp.parent;
//            } else { // tmp是父的右节点
//                tmp.parent.right = tmp.left;
//                tmp.left.parent = tmp.parent;
//            }
//
//        } else { // tmp 2个子节点都不空
//            successor = findSuccessor(tmp);
//            successorParent = successor.parent;
//
//            successor.parent = tmp.parent;
//            if (tmp.parent.left == tmp) {
//                tmp.parent.left = successor;
//            }
//            if (tmp.parent.right == tmp) {
//                tmp.parent.right = successor;
//            }
//
//            if (successor.left != null) {
//                if (successor == successorParent.left) {
//                    successorParent.left = successor.left;
//                    successor.left.parent = successorParent;
//                } else {
//                    successorParent.right = successor.left;
//                    successor.left.parent = successorParent;
//                }
//            } // successor不可能有右节点
//
//            tmp.left.parent = successor;
//            successor.left = tmp.left;
//            tmp.right.parent = successor;
//            successor.right = tmp.right;
//            if (successorParent.right == successor) {
//                successorParent.right = null;
//            }
//        }
//    }

    public void remove(int key) {
        if (root == null) {
            return;
        }
        Node tmp = root;
        while (tmp != null) {
            if (tmp.key == key) {
                break;
            } else if (tmp.key > key) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }
        if (tmp == null) { // 没找到
            return;
        }
        remove(tmp);
    }

    public void remove(Node node) {
        Node replace, child, parent;
        boolean color;

        // 2个子节点都不空
        if (node.left != null && node.right != null) {
            replace = findSuccessor(node);
            parent = replace.parent;
            child = replace.left;
            color = replace.color;
            // node.parent和replace关联
            if (root == node) {
                root = replace;
            } else {
                if (node.parent.left == node) {
                    node.parent.left = replace;
                } else {
                    node.parent.right = replace;
                }
            }

            if (parent == node) { // replace可能是node的直接子节点,也可能是子孙节点
                parent = replace;
            } else {
                parent.right = child;
                replace.left = node.left; // replace是node的直接子节点的话 node.left = replace所以就没必要设置了.只有是孙子节点才需要设置这个
                node.left.parent = replace;
            }
            // child和parent关联
            if (child != null) {
                child.parent = parent;
            }
            // node right和replace关联
            replace.parent = node.parent;
            replace.color = node.color;
            replace.right = node.right;
            node.right.parent = replace;

            if (color == BLACK) {
                removeFix(child, parent);
            }
            return;
        }

        if (node.left != null) {
            child = node.left;
        } else {
            child = node.right;
        }
        color = node.color;
        parent = node.parent;
        if (node == root) {
            root = child;
        } else {
            if (parent.left == node) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        if (child != null) {
            child.parent = parent;
        }
        if (color == BLACK) {
            removeFix(child, parent);
        }
    }

    public void removeFix(Node node, Node parent) {
        Node brother;
        int debugCnt = 1;
        System.out.println(node + "  " + parent);
        while ((node == null || isBlack(node)) && node != root) {
            debugCnt++;
            if (parent.left == node) {
                //x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
                //(01) 将x的兄弟节点设为“黑色”。
                //(02) 将x的父节点设为“红色”。
                //(03) 对x的父节点进行左旋。
                //(04) 左旋后，重新设置x的兄弟节点。
                brother = parent.right;
                if (isRed(brother)) {
                    setBlack(brother);
                    setRed(parent);
                    rotateLeft(parent);
                    continue;
                }

                // x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
                // (01) 将x的兄弟节点设为“红色”。
                //(02) 设置“x的父节点”为“新的x节点”。
                if (isBlack(brother) && isBlack(brother.left) && isBlack(brother.right)) {
                    setRed(brother);
                    node = parent;
                    parent = node.parent;
                    continue;
                }

                // x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
                // (01) 将x兄弟节点的左孩子设为“黑色”。
                //(02) 将x兄弟节点设为“红色”。
                //(03) 对x的兄弟节点进行右旋。
                //(04) 右旋后，重新设置x的兄弟节点。
                if(isBlack(brother) && isRed(brother.left) && isBlack(brother.right)) {
                    setBlack(brother.left);
                    setRed(brother);
                    rotateRight(brother);
                    continue;
                }

                // x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
                // (01) 将x父节点颜色 赋值给 x的兄弟节点。
                //(02) 将x父节点设为“黑色”。
                //(03) 将x兄弟节点的右子节设为“黑色”。
                //(04) 对x的父节点进行左旋。
                //(05) 设置“x”为“根节点”。
                if(isBlack(brother) && isRed(brother.right)) {
                    brother.color = colorOf(parent);
                    setBlack(parent);
                    setBlack(brother.right);
                    rotateLeft(parent);
                    node = root;
                }

            } else {
                brother = parent.left;
                if (isRed(brother)) {
                    setBlack(brother);
                    setRed(parent);
                    rotateRight(parent);
                    continue;
                }

                if (isBlack(brother) && isBlack(brother.left) && isBlack(brother.right)) {
                    setRed(brother);
                    node = parent;
                    parent = node.parent;
                    continue;
                }

                if(isBlack(brother) && isRed(brother.left) && isBlack(brother.right)) {
                    setBlack(brother.right);
                    setRed(brother);
                    rotateLeft(brother);
                    continue;
                }

                if(isBlack(brother) && isRed(brother.right)) {
                    brother.color = colorOf(parent);
                    setBlack(parent);
                    setBlack(brother.left);
                    rotateRight(parent);
                    node = root;
                }


            }
        }

        if (node != null) {
            setBlack(node);
        }
        System.out.println("fixRemove Cnt:" + debugCnt);
    }

    /**
     * 找到接班人, 1.左的最右 2.右的最左
     *
     * @param n
     * @return
     */
    public Node findSuccessor(Node n) {
        Node result = null;
        Node left = n.left;
        Node right = n.right;
        while (left != null) {
            result = left;
            left = left.right;
        }
        if (result != null) {
            return result;
        }

        while (right != null) {
            result = right.left;
            right = right.left;
        }
        return result;

    }


    static class Node implements TreePrintUtil.TreeNode {
        int key;
        Node left;
        Node right;
        Node parent;
        boolean color = RED;


        @Override
        public String getPrintInfo() {
            return key + "";
        }

        @Override
        public TreePrintUtil.TreeNode getLeftChild() {
            return left;
        }

        @Override
        public TreePrintUtil.TreeNode getRightChild() {
            return right;
        }

        public String toString() {
            return "[" + key + "]";
        }
    }
}
